class BinaryTree:

    def __init__(self, val, dist = 0,
                 left:"BinaryTree" = None,
                 right:"BinaryTree" = None):
        self.value = val
        self.distance = dist
        self.left = left
        self.right = right
        
    def get_cluster(self) -> list:
        res = []
        if self.value >= 0:
            res.append(self.value)
        else:
            if (self.left != None):
                res.extend(self.left.get_cluster())
            if (self.right != None): 
                res.extend(self.right.get_cluster())
        return res
    
    def print_tree(self):
        self.print_tree_rec(0, "Root")
    
    def print_tree_rec (self, level, side):
        tabs = "\t"*level
        if self.value >= 0:
            print(tabs, side, " - value:", self.value)
        else:
            print(tabs, side, "- Dist.: ", self.distance)
            if (self.left != None): 
                self.left.print_tree_rec(level+1, "Left")
            if (self.right != None): 
                self.right.print_tree_rec(level+1, "Right")   

def test():              
    a = BinaryTree(1)
    b = BinaryTree(2)
    c = BinaryTree(3)
    d = BinaryTree(4)
    e = BinaryTree(-1, 2.0, b, c)
    f = BinaryTree(-1, 1.5, d, a)
    g = BinaryTree(-1, 4.5, e, f)
    g.print_tree()
    print(g.get_cluster())

    # testing exercise 3
    # print(g.size())
    # print(g.exists_leaf(1))
    # print(g.exists_leaf(5))
    # g.common_ancestor(1,4).print_tree()
    # print(g.distance_leaves(1,4))
    # print(g.distance_leaves(1,2))

if __name__ == '__main__':
    test()
